Khi chơi bóng đá trẻ cho Frederiksberg Boldklub, Elkjær đã có màn ra mắt cho đội tuyển quốc gia lứa tuổi U19 Đan Mạch vào tháng 10 năm 1975. Ông đã có tổng cộng 11 trận và ghi được 6 bàn thắng, trong đó có 3 trận thi đấu ở Giải vô địch bóng đá U-19 châu Âu năm 1975.[9]

Ông có lần đầu ra mắt U21 Đan Mạch vào tháng 6 năm 1976,[9] có 9 bàn thắng sau 9 trận, trong đó có 3 bàn ghi được tại tứ kết của Giải vô địch bóng đá U-21 châu Âu 1978 gặp Bulgaria, mặc dù Đan Mạch đã bị loại do luật bàn thắng sân khách.[9]

Vào ngày 22 tháng 6 năm 1977, khi mới 19 tuổi 284 ngày, Elkjær ra mắt đội tuyển bóng đá quốc gia Đan Mạch, và ghi được cả hai bàn trong chiến thắng của Đan Mạch trước Phần Lan. Ông có vai trò quan trọng tại EURO 1984, ghi được 2 bàn thắng trong 4 trận,[9] mở đường cho việc sang thi đấu tại Ý.[10] Tại giải đấu, Đan Mạch chơi thứ bóng đá tấn công hấp dẫn, nhưng đã bị loại ở vòng bán kết sau khi thua Tây Ban Nha trên chấm phạt đền.[9] Elkjær là cầu thủ đá phạt đền cuối cùng của Đan Mạch nhưng bóng đi vọt xà ngang.[11]

Elkjær cũng có mặt trong đội hình Đan Mạch tại FIFA World Cup 1986 khi Đan Mạch lần đầu tiên vượt qua vòng sơ loại. Tại giải đấu đó, Đan Mạch đã vượt qua vòng đấu bảng với tư cách nhất bảng nhưng một lần nữa dừng chân bởi những người Tây Ban Nha.[9] Riêng cá nhân Elkjær đã ghi được 4 bàn thắng, trong đó có một cú hat-trick vào lưới Uruguay.[9] Được đánh giá là tiền đạo năng động và mạnh mẽ nhất giải đấu,[12] ông xếp vị trí thứ ba trong cuộc đua Quả bóng Vàng World Cup 1986.[13]

Euro 1988 là giải đấu cuối cùng Elkjær thi đấu cho đội tuyển quốc gia. Vào ngày 14 tháng 6 năm 1988, ông thi đấu trận cuối cùng trong màu áo đội tuyển quốc gia, khi đó ông 30 tuổi 277 ngày, trong trận đấu mà Đan Mạch đã thua Tây Đức với tỉ số 0-2, kết thúc giải đấu với ba trận thua ở vòng bảng. Tổng cộng sự nghiệp ông có 69 trận đấu quốc tế và ghi được 38 bàn thắng.[9]